{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_list = [1.1,1.2,1.3,2.1,2.2,2.3,3.1,3.2,3.3] \n",
    "reversed_list = test_list[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "group_num = len(test_list) // 3\n",
    "print(group_num) # 逻辑中位数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "result = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从指定位置开始切片, [1.1, 1.3, 2.2, 3.1, 3.3]\n",
      "指定位置切片后取对应数量 [1.1]\n",
      "从指定位置开始切片, [1.2, 2.1, 2.3, 3.2]\n",
      "指定位置切片后取对应数量 [1.2, 2.1]\n",
      "从指定位置开始切片, [1.3, 2.2, 3.1, 3.3]\n",
      "指定位置切片后取对应数量 [1.3, 2.2, 3.1]\n"
     ]
    }
   ],
   "source": [
    "# 顺序遍历得到结果\n",
    "for round in range(group_num):\n",
    "    # print(round) #  0 1 2\n",
    "    # 相对位置切片访问\n",
    "    # print(test_list[round::2])\n",
    "    temp = test_list[round::2]\n",
    "    print(\"从指定位置开始切片,\",temp)\n",
    "    temp_result = temp[:round+1]\n",
    "    print(\"指定位置切片后取对应数量\",temp_result)\n",
    "    if round % 2 == 0: \n",
    "        temp = temp_result[::-1]\n",
    "        for item in temp:\n",
    "            result.append(item)\n",
    "    else:\n",
    "        for item in temp_result:\n",
    "            result.append(item)\n",
    "# print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [],
   "source": [
    "temp_reverse = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从指定位置开始切片, [3.3, 3.1, 2.2, 1.3, 1.1]\n",
      "指定位置切片后取对应数量 [3.3]\n",
      "从指定位置开始切片, [3.2, 2.3, 2.1, 1.2]\n",
      "指定位置切片后取对应数量 [3.2, 2.3]\n",
      "从指定位置开始切片, [3.1, 2.2, 1.3, 1.1]\n",
      "指定位置切片后取对应数量 [3.1, 2.2, 1.3]\n"
     ]
    }
   ],
   "source": [
    "for round in range(group_num):\n",
    "    # print(test_list[round::2])\n",
    "    temp = reversed_list[round::2]\n",
    "    print(\"从指定位置开始切片,\",temp)\n",
    "    temp_result = temp[:round+1]\n",
    "    print(\"指定位置切片后取对应数量\",temp_result)\n",
    "    if round % 2 == 0: \n",
    "        # 偶数 直接加入答案\n",
    "        for item in temp_result:\n",
    "            temp_reverse.append(item)\n",
    "    else:\n",
    "        temp = temp_result[::-1]\n",
    "        for item in temp:\n",
    "            temp_reverse.append(item)\n",
    "temp_reverse_reverser = temp_reverse[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1.3, 2.2, 3.1, 3.2, 2.3, 3.3]\n"
     ]
    }
   ],
   "source": [
    "print(temp_reverse_reverser)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [],
   "source": [
    "if group_num % 2 == 0:\n",
    "    # 偶数的情况全部加入结果\n",
    "    for item in temp_reverse_reverser:\n",
    "        result.append(item)\n",
    "else:\n",
    "    temp = temp_reverse_reverser[1:]\n",
    "    for item in temp:\n",
    "        # 奇数的情况第一个元素不要加入其中\n",
    "        result.append(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1.1, 1.2, 2.1, 3.1, 2.2, 1.3, 2.2, 3.1, 3.2, 2.3, 3.3]\n"
     ]
    }
   ],
   "source": [
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_solution(line_mat_list):\n",
    "    group_num = len(line_mat_list) // 3\n",
    "    reversed_list = line_mat_list[::-1]\n",
    "    result = []\n",
    "    # 顺序遍历得到结果\n",
    "    for round in range(group_num):\n",
    "        temp = line_mat_list[round::2]\n",
    "        temp_result = temp[:round+1]\n",
    "        if round % 2 == 0: \n",
    "            temp = temp_result[::-1]\n",
    "            for item in temp:\n",
    "                result.append(item)\n",
    "        else:\n",
    "            for item in temp_result:\n",
    "                result.append(item)\n",
    "    # print(result)\n",
    "    temp_reverse = []\n",
    "    for round in range(group_num):\n",
    "        temp = reversed_list[round::2]\n",
    "        temp_result = temp[:round+1]\n",
    "        if round % 2 == 0: \n",
    "            # 偶数 直接加入答案\n",
    "            for item in temp_result:\n",
    "                temp_reverse.append(item)\n",
    "        else:\n",
    "            temp = temp_result[::-1]\n",
    "            for item in temp:\n",
    "                temp_reverse.append(item)\n",
    "    temp_reverse_reverser = temp_reverse[::-1]\n",
    "    if group_num % 2 == 0:\n",
    "        # 偶数的情况全部加入结果\n",
    "        for item in temp_reverse_reverser:\n",
    "            result.append(item)\n",
    "    else:\n",
    "        temp = temp_reverse_reverser[1:]\n",
    "        for item in temp:\n",
    "            # 奇数的情况第一个元素不要加入其中\n",
    "            result.append(item)\n",
    "    return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1.1, 1.2, 2.1, 3.1, 2.2, 1.3, 2.2, 3.1, 3.2, 2.3, 3.3]\n"
     ]
    }
   ],
   "source": [
    "print(my_solution(test_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最终答案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def my_solution(self,line_mat_list):\n",
    "        reversed_list = line_mat_list[::-1]\n",
    "        group_num = len(line_mat_list) // 3\n",
    "        result = []\n",
    "        # 顺序遍历得到结果\n",
    "        for round in range(group_num):\n",
    "            temp = line_mat_list[round::2]\n",
    "            temp_result = temp[:round+1]\n",
    "            if round % 2 == 0: \n",
    "                temp = temp_result[::-1]\n",
    "                for item in temp:\n",
    "                    result.append(item)\n",
    "            else:\n",
    "                for item in temp_result:\n",
    "                    result.append(item)\n",
    "        temp_reverse = []\n",
    "        for round in range(group_num):\n",
    "            temp = reversed_list[round::2]\n",
    "            temp_result = temp[:round+1]\n",
    "            if round % 2 == 0: \n",
    "                # 偶数 直接加入答案\n",
    "                for item in temp_result:\n",
    "                    temp_reverse.append(item)\n",
    "            else:\n",
    "                temp = temp_result[::-1]\n",
    "                for item in temp:\n",
    "                    temp_reverse.append(item)\n",
    "        temp_reverse_reverser = temp_reverse[::-1]\n",
    "        if group_num % 2 == 0:\n",
    "            # 偶数的情况全部加入结果\n",
    "            for item in temp_reverse_reverser:\n",
    "                result.append(item)\n",
    "        else:\n",
    "            temp = temp_reverse_reverser[1:]\n",
    "            for item in temp:\n",
    "                # 奇数的情况第一个元素不要加入其中\n",
    "                result.append(item)\n",
    "        return result \n",
    "    def findDiagonalOrder(self, mat):\n",
    "        \"\"\"\n",
    "        :type mat: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        line_first_traversal = []\n",
    "        for row in mat:\n",
    "            for item in row:\n",
    "                line_first_traversal.append(item)\n",
    "        return self.my_solution(line_first_traversal)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_solution = Solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_4th_mat = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 2,\n",
       " 4,\n",
       " 7,\n",
       " 5,\n",
       " 3,\n",
       " 4,\n",
       " 6,\n",
       " 8,\n",
       " 10,\n",
       " 13,\n",
       " 11,\n",
       " 9,\n",
       " 7,\n",
       " 5,\n",
       " 6,\n",
       " 8,\n",
       " 10,\n",
       " 12,\n",
       " 13,\n",
       " 11,\n",
       " 9,\n",
       " 7,\n",
       " 10,\n",
       " 12,\n",
       " 14,\n",
       " 15,\n",
       " 13,\n",
       " 16]"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_solution.findDiagonalOrder(test_4th_mat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面是错误的解法，这个解法只能解决一个特殊的3阶的结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_mat = [[1,2,3],[4,5,6],[7,8,9]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_solution(mat):\n",
    "    row_length = len(mat)\n",
    "    col_length = len(mat[0])\n",
    "    rounds = row_length + col_length - 1\n",
    "    result = []\n",
    "    # 一共需要遍历的倾斜次数 物理下标\n",
    "    for round in range(rounds):\n",
    "        # 第一轮的情况下 \n",
    "        if round == 0:\n",
    "            # print(mat[0][0])\n",
    "            result.append(mat[0][0])\n",
    "        # 最后一轮的情况下\n",
    "        if round == rounds-1:\n",
    "            print(mat[row_length-1][col_length-1])\n",
    "            result.append(mat[row_length-1][col_length-1])\n",
    "            break\n",
    "        \"\"\"         \n",
    "        if round % 2 == 0:\n",
    "            # 物理下标偶数的情况 从右上到左下遍历\n",
    "            for index_row in range(round+1):\n",
    "                row_position = index_row                # 选定右上角的行\n",
    "                line_position = round - row_position    # 选定最后一列\n",
    "                #print(\"奇数\",round,row_position,line_position)\n",
    "                #print(mat[row_position][line_position])\n",
    "                result.append(mat[row_position][line_position])\n",
    "        \"\"\"\n",
    "\n",
    "        if round % 2 != 0:\n",
    "            if round < (rounds / 2): \n",
    "                # 物理下标奇数的情况 左下到右上\n",
    "                for index_row in range(round+1):\n",
    "                    col_position = index_row \n",
    "                    row_position = round - col_position\n",
    "                    print(\"奇数\",round,row_position,col_position)\n",
    "                    #print(mat[row_position][line_position])\n",
    "                    result.append(mat[row_position][col_position])\n",
    "            else:\n",
    "                # 已经到达了下半段\n",
    "                for index_row in range(round):\n",
    "                    col_position = index_row + 1\n",
    "                    row_position = round - col_position\n",
    "                    print(\"奇数\",round,row_position,col_position)\n",
    "                    #print(mat[row_position][line_position])\n",
    "                    result.append(mat[row_position][col_position])\n",
    "    return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "奇数 1 1 0\n",
      "奇数 3 2 1\n",
      "奇数 3 1 2\n",
      "奇数 3 0 3\n"
     ]
    },
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[217], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[43mtest_solution\u001b[49m\u001b[43m(\u001b[49m\u001b[43mtest_mat\u001b[49m\u001b[43m)\u001b[49m)\n",
      "Cell \u001b[0;32mIn[216], line 44\u001b[0m, in \u001b[0;36mtest_solution\u001b[0;34m(mat)\u001b[0m\n\u001b[1;32m     42\u001b[0m                 \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m奇数\u001b[39m\u001b[38;5;124m\"\u001b[39m,\u001b[38;5;28mround\u001b[39m,row_position,col_position)\n\u001b[1;32m     43\u001b[0m                 \u001b[38;5;66;03m#print(mat[row_position][line_position])\u001b[39;00m\n\u001b[0;32m---> 44\u001b[0m                 result\u001b[38;5;241m.\u001b[39mappend(\u001b[43mmat\u001b[49m\u001b[43m[\u001b[49m\u001b[43mrow_position\u001b[49m\u001b[43m]\u001b[49m\u001b[43m[\u001b[49m\u001b[43mcol_position\u001b[49m\u001b[43m]\u001b[49m)\n\u001b[1;32m     45\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m result\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "print(test_solution(test_mat))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "for index in range(2):\n",
    "    print(index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这是一种相当有意思的Matrix的遍历，它确实有一种便利的斜向的结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "def test_solution(mat):\n",
    "    lookup_dict = defaultdict(list)\n",
    "    for index_row,row in enumerate(mat):\n",
    "        for index_col,col_item in enumerate(row):\n",
    "            lookup_dict[index_row+index_col].append(col_item)\n",
    "    return lookup_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "defaultdict(<class 'list'>, {0: [1], 1: [2, 4], 2: [3, 5, 7], 3: [6, 8], 4: [9]})\n"
     ]
    }
   ],
   "source": [
    "standard_mat = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "processed_mat = test_solution(standard_mat)\n",
    "print(processed_mat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这是非常有意思的，在Interaction的时候，List就是Index和Value，类似的，Dict就是Key和Value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 [1]\n",
      "1 [2, 4]\n",
      "2 [3, 5, 7]\n",
      "3 [6, 8]\n",
      "4 [9]\n"
     ]
    }
   ],
   "source": [
    "for key,value in processed_mat.items():\n",
    "    print(key,value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 7, 5, 3, 6, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "direction_result = []\n",
    "direction_flag = False\n",
    "for key,value in processed_mat.items():\n",
    "    if direction_flag == False:\n",
    "        # 偶数的不变\n",
    "        direction_result.extend(value[::-1])\n",
    "        direction_flag = True\n",
    "    else:\n",
    "        # 奇数的逆向\n",
    "        direction_result.extend(value)\n",
    "        direction_flag = False\n",
    "print(direction_result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构造最终答案\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        lookup_dict = defaultdict(list)\n",
    "        for index_row,row in enumerate(mat):\n",
    "            for index_col,col_item in enumerate(row):\n",
    "                lookup_dict[index_row+index_col].append(col_item)\n",
    "        direction_result = []\n",
    "        direction_flag = False\n",
    "        for key,value in lookup_dict.items():\n",
    "            if direction_flag == False:\n",
    "                # 偶数的不变\n",
    "                direction_result.extend(value[::-1])\n",
    "                direction_flag = True\n",
    "            else:\n",
    "                # 奇数的逆向\n",
    "                direction_result.extend(value)\n",
    "                direction_flag = False\n",
    "        return direction_result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果是按照斜线的数量作为解空间的大小，我们这么考虑一下"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 236,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix: # 边界处理\n",
    "            return []  \n",
    "        row = len(matrix)       # 行数\n",
    "        col = len(matrix[0])    # 列数\n",
    "\n",
    "        tot = row + col - 1 # 对角线条数\n",
    "        res = []            # 结果预先设置为空列表\n",
    "        r, c = 0, 0         # r为横坐标，c为纵坐标\n",
    "\n",
    "        for i in range(tot): \n",
    "            # 遍历对角线条数\n",
    "            '''\n",
    "                上边界r=0、左边界c=0、右边界c=col-1、下边界r=row-1\n",
    "            '''\n",
    "            if i % 2 == 0: # 偶数时，向右上遍历\n",
    "                while r >= 0 and c < col: \n",
    "                # 右上遍历，横坐标不超过上边界且纵坐标不超过右边界\n",
    "                    res.append(matrix[r][c])\n",
    "                    r -= 1 # 横坐标向上移动一格\n",
    "                    c += 1 # 纵坐标向右移动一格\n",
    "                if c < col:\n",
    "                    # 判断c是否超出右边界，如果没有超出则r+=1把r横坐标拉回上边界\n",
    "                    # 已经遍历完一条对角线后，把坐标点放到下一个对角线的起始点上\n",
    "                    r += 1\n",
    "                else:\n",
    "                    # 最中间的一条的情况\n",
    "                    # c -= 1拉回到右边界，r += 2（一共2格，回到原来超出前位置算一格，往下走一格\n",
    "                    r += 2\n",
    "                    c -= 1\n",
    "            else: \n",
    "                # 对角线向左下遍识历\n",
    "                while c >= 0 and r < row: \n",
    "                    res.append(matrix[r][c])\n",
    "                    r += 1\n",
    "                    c -= 1\n",
    "\n",
    "                if r < row:\n",
    "                    c += 1\n",
    "                else:\n",
    "                    c += 2\n",
    "                    r -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 237,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 5, 8, 0, 4, -1]"
      ]
     },
     "execution_count": 237,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_solution = Solution()\n",
    "my_solution.findDiagonalOrder([[2,5],[8,4],[0,-1]])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "science39",
   "language": "python",
   "name": "science39"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
